package com.leetcode;

import com.leetcode.common.TreeNode;
import com.leetcode.util.BinaryTreeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 103. 二叉树的锯齿形层序遍历
 * 递归深度优先搜索, 传递节点所在的层, 根据层level来计算是否优先左或者右子树搜索
 *
 * 如果上层节点已经被反转了. 下层如果在不节点同一侧, 则无法再正序遍历. 所以这个方法行不通有问题
 *
 * @author fy
 * @date 2022/4/15 9:03
 */
public class Solution103_2 {

    private List<List<Integer>> res;

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        res = new ArrayList<>();
        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        if (level == res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(node.val);
        int nextLevel = level + 1;
        boolean orderLeft = nextLevel % 2 == 0;
        if (orderLeft) {
            dfs(node.left, nextLevel);
            dfs(node.right, nextLevel);
        } else {
            dfs(node.right, nextLevel);
            dfs(node.left, nextLevel);
        }
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1, 2, 3, 4, null, null, 5};
        TreeNode root = BinaryTreeUtil.createTree(nums);
        BinaryTreeUtil.printTree(root);

        List<List<Integer>> res = new Solution103_2().zigzagLevelOrder(root);
        System.out.println(res);
    }

}
